package com.algorithm.code.graph;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 1. 无向图
 * 2. 采用连接表实现
 *
 * @program: study
 * @className: UndirectedGraph
 * @description: TODO
 * @author: kukuxiahuni
 * @create: 2020-02-06 19:22
 **/
public class UndirectedGraph {

    /**
     * 顶点个数
     */
    private int vertexCount;

    /**
     * 邻接表
     */
    private LinkedList<Integer>[] adjacencyTable;

    /**
     * 构造函数
     *
     * @method:
     * @param:
     * @return:
     * @author: kukuxiahuni
     * @create: 2020/2/6 19:27
     * @modify_user:TODO
     * @modify_time: 2020/2/6 19:27
     **/
    public UndirectedGraph(int vertexCount) {
        this.vertexCount = vertexCount;
        this.adjacencyTable = new LinkedList[vertexCount];
        for (int i = 0; i < this.vertexCount; ++i) {
            this.adjacencyTable[i] = new LinkedList<>();
        }

    }

    /**
     * 注意其为无向图
     * 添加节点关系
     *
     * @param from :出发点
     * @param to   ：结束点
     */
    public void add(int from, int to) {

        this.adjacencyTable[from].add(to);
        this.adjacencyTable[to].add(from);

    }

    /**
     * @method: 从指定顶点vertex开始，进行广度优先搜索，并打印数据
     * @param:
     * @return:
     * @author: kukuxiahuni
     * @create: 2020/2/6 19:48
     * @modify_user:TODO
     * @modify_time: 2020/2/6 19:48
     **/
    public void bfs(int vertex) {

        /**
         * 访问数组，标记顶点是否被访问过，如果被访问了，则不进行访问
         */
        boolean[] visited = new boolean[this.vertexCount];
        Arrays.fill(visited, false);

        Queue<Integer> queue = new LinkedList<>();
        queue.add(vertex);
        visited[vertex] = true;
        System.out.print(vertex + " -> ");

        while (!queue.isEmpty()) {
            int queuedVertex = queue.poll();
            //将该节点的邻接节点加入到队列中

            LinkedList<Integer> adjacencyList = this.adjacencyTable[queuedVertex];
            for (int adjaVertex : adjacencyList) {
                if (!visited[adjaVertex]) {
                    System.out.print(adjaVertex + " -> ");
                    queue.add(adjaVertex);
                    visited[adjaVertex] = true;
                }
            }

        }
    }

    /**
     * 
     */
    public final void dfs() {
        
    }

    public static void main(String[] args) {
        UndirectedGraph graph = new UndirectedGraph(5);
        graph.add(1, 3);
        graph.add(1, 2);
        graph.add(2, 3);
        graph.add(2, 4);
//        graph.add(3, 4);

        graph.bfs(3);
    }
}
